package leetcode;

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {

    public static void main(String[] args) {
        GenerateParentheses g = new GenerateParentheses();
        List<String> strings = g.backtrackGenerateParenthesis(3);
        System.out.println(strings);
    }

    private List<String> backtrackGenerateParenthesis(int i) {
        List<String> list = new ArrayList<>();
        gen(0, 0, list, new StringBuilder(""), i);
        return list;
    }

    private void gen(int open, int close, List<String> list, StringBuilder s, int i){
        if(s.length() == i * 2){
            list.add(s.toString());
        }else{
            if(open < i){
                s.append("(");
                gen(open + 1, close, list, s, i);
                s.deleteCharAt(s.length() - 1);
            }
            if(open > close){
                s.append(")");
                gen(open, close + 1, list, s, i);
                s.deleteCharAt(s.length() - 1);
            }
        }
    }


//    ============================================================================================================================

    private List<String> forceGenerateParenthesis(int i) {
        List<String> list = new ArrayList<>();
        gen(list, new char[i * 2], 0);
        return list;
    }

    private void gen(List<String> list, char[] chars, int pod) {
        if(pod == chars.length){
            if(valid(chars)){
                list.add(new String(chars));
            }
        }else{
            chars[pod] = '(';
            gen(list, chars, pod + 1);
            chars[pod] = ')';
            gen(list, chars, pod + 1);
        }

    }

    private boolean valid(char[] chars) {
        int balance = 0;
        for (int i = 0; i < chars.length; i++) {
            if(chars[i] == '('){
                ++balance;
            }else{
                -- balance;
            }
            if(balance <0 ) return false;
        }
        return balance == 0;
    }


}
